package day_2022_7_to_8.day48;

import java.util.*;

/**
 * @author haomin
 * @date 2022/08/04 10:29
 **/
public class Day20_1_Num1403_MinSubsequence {
    public static void main(String[] args) {
        int[] arr = {73,71,26,65,53,63,46,54,45,1,69,70,80,79,43,59,77,4,30,82,23,71,75,24,12,71,33,5,87,10,11,3,58,2,97,97,36,32,35,15,80,24,45,38,9,22,21,33,68,22,85,35,83,92,38,59};
        minSubsequence(arr);
    }
    public static List<Integer> minSubsequence(int[] nums) {
        List<Integer> list = new ArrayList<>();
        insertSort(nums);  // 倒排

        int total = 0, sum = 0;
        for (int num : nums) total+=num;
        for (int num : nums) {
            sum+=num; list.add(num);
            if(sum > total/2) break;
        }
        return list;
    }
    // 直接插入排序
    private static void insertSort(int[] nums) {
        for(int i = 0;i < nums.length;i++){
            for(int j = i; j > 0 && nums[j] > nums[j-1];j--){
                int temp = nums[j];nums[j] = nums[j-1];nums[j-1] = temp;
            }
        }
    }
}